package 数据结构和算法.剑指offer.树.从上到下打印二叉树I;

import 数据结构和算法.数据结构.普通二叉树.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 从上到下打印二叉树
 * <p>
 * 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如:
 * 给定二叉树: [3,9,20,null,null,15,7]
 * <p>
 * 通常二叉树的问题使用递归较多，而对于本题分层打印二叉树而言，
 * 使用广度优先策略（BFS）会更好一些。
 * 算法的思路是使用队列的先入先出特性将二叉树的结点值放入队列，再输出到新的数组中
 */
public class Test {
    public static int[] levelOrder(TreeNode root) {
        List<Integer> resList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        if (null == root) {
            return new int[0];
        }

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            resList.add(node.getValue());
            if (node.getLeftTreeNode() != null) {
                queue.add(node.getLeftTreeNode());
            }
            if (node.getRightTreeNode() != null) {
                queue.add(node.getRightTreeNode());
            }
        }

        int[] array = new int[resList.size()];
        for (int i = 0; i < resList.size(); ++i) {
            array[i] = resList.get(i);
        }

        return array;
    }
}
